import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵 Spiral Matrix
 * https://leetcode.cn/problems/spiral-matrix/
 */
class SpiralMatrix {
    //右下左上
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 
    /**
     * 方法：spiralOrder
     * 按照顺时针螺旋顺序遍历二维矩阵
     * 
     * Args:
     * matrix: 二维整型数组，表示要遍历的矩阵
     * 
     * Returns:
     * List<Integer>: 按螺旋顺序排列的矩阵元素列表
     * 
     * Time: O(m*n)，其中m是矩阵行数，n是矩阵列数
     * Space: O(1)，除了返回结果外，只使用了常数级别的额外空间
     *
     * 由于走的步数是有规律的，我们可以精确地控制在每个方向上要走多少步，无需判断是否出界、是否重复访问：
     *
     * 从 (0,−1) 开始。
     * 一开始，向右走 n 步，每次先走一步，再把数字加入答案。走 n 步即 1→2→3→4，矩阵第一排的数都加入了答案。
     * 然后向下走 m−1 步，即 8→12。
     * 然后向左走 n−1 步，即 11→10→9。
     * 然后向上走 m−2 步，即 5。
     * 然后向右走 n−2 步，即 6→7。
     * 重复上述过程，直到答案的长度等于 mn。
     * 代码实现时，可以这样简化代码：
     *
     * 一开始走 n 步。
     * 把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 m−1 步），无需修改其他逻辑。
     * 把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 n−1 步）。
     * 把 n,m 分别更新为 m−1,n，这样下一轮循环又可以走 n 步（相当于走了 m−2 步）。
     * 依此类推，每次只需把 n,m 分别更新为 m−1,n 即可。
     *
     * 作者：灵茶山艾府
     * 链接：https://leetcode.cn/problems/spiral-matrix/solutions/2966229/liang-chong-fang-fa-jian-ji-gao-xiao-pyt-4wzk/
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int size = m * n;
        List<Integer> ans = new ArrayList<>(size);
        int i = 0;
        int j = -1;
        for(int di = 0; ans.size()< size; di = (di + 1) % 4){
            for(int k = 0; k < n; k++){// 走 n 步（注意 n 会减少）
                i += DIRS[di][0];
                j += DIRS[di][1];
                ans.add(matrix[i][j]);
            }
            int tmp = n;
            n = m - 1; // 减少后面的循环次数（步数）
            m = tmp;
        }
        return ans;
    }

    /**
     * 方法：spiralOrder1
     * 按照顺时针螺旋顺序遍历二维矩阵（边界收缩法）
     * 
     * Args:
     * matrix: 二维整型数组，表示要遍历的矩阵
     * 
     * Returns:
     * List<Integer>: 按螺旋顺序排列的矩阵元素列表
     * 
     * Time: O(m*n)，其中m是矩阵行数，n是矩阵列数
     * Space: O(1)，除了返回结果外，只使用了常数级别的额外空间
     */
    public List<Integer> spiralOrder1(int[][] matrix) {
        if(matrix.length == 0){
            return new ArrayList<>();
        }
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        List<Integer> res = new ArrayList<>();
        while(top <= bottom && left <= right){
            // 从左到右遍历顶层
            for(int j = left; j <= right; j ++){
                res.add(matrix[top][j]);
            }
            top++;
            // 从上到下遍历右列
            for(int i = top; i <= bottom; i++){
                res.add(matrix[i][right]);
            }
            right--;
            if(top <= bottom){
                // 从右到左遍历底层
                for(int j = right; j >= left; j--){
                    res.add(matrix[bottom][j]);
                }
                bottom--;
            }
            if(left <= right){
                // 从下到上遍历左列
                for(int i = bottom; i >= top; i--){
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }
}